package T21_30;

public class T30 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        /*思路：1 链表分为已反转部分，待返转部分，未反转部分
        * 2 定义虚拟头结点
        * 3 定义start指向待返转部分的第一个节点，end指向待返转部分的最后一个结点，pre指向start的前驱
        * 4 执行完反转操作之后，pre指向end(此时的end由于翻转，所以实际是start)*/
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        ListNode pre=dummy;
        ListNode end=dummy;
        while (end.next!=null){
            for (int i = 0; i < k&&end!=null; i++) {
                end=end.next;
            }
            if (end==null)break;
            ListNode start=pre.next;
            ListNode next=end.next;
            end.next=null;
            pre.next=reverse(start);
            //反转之后start和end的指向结点没有改变，改变的是位置
            start.next=next;
            //将pre，end指向待反转链表头结点的前一个结点
            pre=start;
            end=pre;
        }
        return dummy.next;
    }
    //反转链表
    private ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode curr=head;
        while(curr!=null){
            ListNode next=curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }
}